# 2nd Try, Test-Driven Sudoku Development
# The essential idea behind this implementation is the exact cover.
# It is modelled as a series of constraints, to which options fulfill a few of those constraints
# So basically, all you need to do is describe the constraints, describe the options and which 
# constraints they satisfy, remove both from the list, and keep doing this until no more options are
# available, or no more constraints need to be satisfied. You can do a depth first search of all the
# options in sequence, basically brute forcing your way through the problem. However, with linked 
# lists, this can actually be pretty quick. 
# Based on Algorithm X

# To illustrate the construction of m, it is a map of group numbers to particular cells. For an i x i game
# we should see exactly i groups with i spots in each group. Sudoku is an example of this. 
# The following is what m should look like for Sudoku
#
#    1  2  3  4  5  6  7  8  9
# 1  1  1  1  2  2  2  3  3  3
# 2  1  1  1  2  2  2  3  3  3
# 3  1  1  1  2  2  2  3  3  3
# 4  4  4  4  5  5  5  6  6  6
# 5  4  4  4  5  5  5  6  6  6
# 6  4  4  4  5  5  5  6  6  6
# 7  7  7  7  8  8  8  9  9  9
# 8  7  7  7  8  8  8  9  9  9
# 9  7  7  7  8  8  8  9  9  9

STD_BOX_MATRIX = [[1,1,1,4,4,4,7,7,7],
                  [1,1,1,4,4,4,7,7,7], 
                  [1,1,1,4,4,4,7,7,7], 
                  [2,2,2,5,5,5,8,8,8], 
                  [2,2,2,5,5,5,8,8,8], 
                  [2,2,2,5,5,5,8,8,8], 
                  [3,3,3,6,6,6,9,9,9], 
                  [3,3,3,6,6,6,9,9,9], 
                  [3,3,3,6,6,6,9,9,9]]

class Node
	attr_accessor :constraints
    attr_reader :xPosition
    attr_reader :yPosition
    attr_reader :value
    def initialize(x,y,v)
        @constraints = []
        @xPosition = x
        @yPosition = y
        @value = v
    end
    def addConstraint(c)
        @constraints.push(c)
    end
    def ==(o)
        o.class == self.class && o.state == state
    end
    def state 
        [@xPosition, @yPosition, @value]
    end
    def to_s
        "<#{node.xPosition}, #{node.yPosition}, #{node.value}>"
    end
end

class Constraint
    attr_accessor :nodes
    attr_accessor :row
    attr_accessor :group
    attr_accessor :column
    attr_accessor :value
    attr_accessor :filled
    attr_reader :description
    def initialize(d = '')
        @nodes = []
        @description = d
    end
    def addNode(n)
        @nodes.push(n)
    end
    def to_s        
        result = self.description + "\n"
        result << "(#{self.column}, #{self.row}) filled\n" if self.filled
        for s in [:group, :column, :row, :value] do
            result << s.to_s << ": " << self.send(s).to_s << "\n" if self.send(s)
        end
        result
    end
end

def preloadPuzzle(a, nodes, constraints)
    debug = false
    #requires 2D Array a size [i][i] where a[i][j] = [0-i] for all i and j
    #0 corresponds to an unsolved square.
    #also requires a set of nodes
    #
    #returns a list of nodes that correspond to those filled in on the input puzzle a
    if debug then
        print "preloading puzzle - node length   = ", nodes.length, ", constraints.length = " 
        print constraints.length, ", a.length = ", a.length, "\n"
    end
    solution =[]
    (1..a.length).each do |x|
        (1..a.length).each do |y|
            v = a[x-1][y-1]
            unless v == 0
                foundNodes = findNodes(nodes, x, y, v)
                foundNodes.each do |n| 
                    solution.push(n)
                    removeNode(n, constraints)
                end
            end
        end
    end
    solution
end

def addToStack(nodes, stack, i)
    # requires a stack on which to throw the nodes. Also, an integer
    # to pair with the nodes. This will indicate how far the 
    # solution was along when this choice was added to the stack.
    # stack = #stack union nodes
    debug = false
    
    nodes.each do |n|
        if debug and nodes.length > 1
            print "Adding node "
            puts n.to_s
            print " with backtrack point ", i, "\n"
        end
        pair = [n, i]
        stack.push(pair)
    end
end

def solvePuzzle(a, m) 
    #requires 2D Array a size [i][i] where a[i][j] = [0-i] for all i and j
    #0 corresponds to an unsolved square.
    #also requires a second 2D array where |m| = |a| and in which m[i][j]= n where n = [0-i] and exactly
    #i elements in m are equal to n for each value of n.
    #
    #The first array corresponds to the initial conditions. The constraints are defined by the rows, 
    #columns and the second array. The second array defines i groups of i elements in which each element
    #corresponds to a single position in the first array. This is a third dimension of constraint and 
    #could be modelled by a third dimension in the initial array. However, a third dimension would 
    #not be quite accurate, as the position in the third constraint is dictated by the position in the 
    #row and columns. It is more accurate to imagine this third constraint as some arbitrary grouping of
    #boxes in the initial array such that there are i groups and i boxes in each group
    #
    #returns array filled such that for each digit d from 1..i, and for each x there exists some 
    #a[x][y] = d
    #and for each q there exists some a[p][q] = d 
    #and for each number n in 1..i and each i in m[i][j] there exists some j such that m[i][j] = (x,y)
    #where a[x][y] = n
    debug = false
    nodes = getNodes(m.length)
    
    #create all constraints for a puzzle of size a.length
    constraints = getConstraints(m.length)

    #assign nodes and constraints
    assignNodesToConstraints(nodes, constraints, makeGroupList(m))
    
    solution = preloadPuzzle(a, nodes, constraints)

    nodeStack = []
    solved = constraints.length == 0
    
    firstConstraint = findNextConstraint(constraints) unless solved
    #add all nodes from this constraint's list to the stack. This would be all 
    #possible nodes that could fulfil it
    addToStack(firstConstraint.nodes, nodeStack, solution.length) unless solved
    
    until solved
        #get first pair of node and backtrack point off the stack. 
        pair = nodeStack.pop()
        currentNode = pair[0]        
        
        #add it to the solution. 
        solution.push(currentNode)
        
        #Once a node is removed, you must remove all options that could have fulfilled
        #its constraints from other lists of constraints that they fulfil. For example,
        #if you place a 1 in the 1,1 spot, you cannot also place it in the 1,2 spot. 
        #This is modelled by the fact that both share the constraint 'column 1 needs a
        #1' and you can get to the 1,2,1 node by going through that constraint's list.
        #This is all handled by the removeNode function, which relies on helpers
        removeNode(currentNode, constraints)
        solved = true if constraints.length == 0
        break if constraints.length == 0
        #Then we must pick a new constraint.
        nextConstraint = findNextConstraint(constraints)
        #if the nextConstraint's node length is 0, this means there are no possible options that can satisfy it and we 
        #must backtrack
        if nextConstraint.nodes.length == 0
            backtrackPoint = nodeStack[nodeStack.length - 1][1]
            backtrack(solution, backtrackPoint, constraints)
        else
            #We add each of the nextConstraint's nodes to the stack and continue
            addToStack(nextConstraint.nodes, nodeStack, solution.length)
            
        end
    end

    print "Solution length = ", solution.length, "\n" if debug
    puts "No Solution Possible!" unless solved
    
    #output as a 2D array
    turnSolutionIntoArray(solution, a.length)
end

def turnSolutionIntoArray(solution, i)
    #requires solution be a 1D array of Nodes where for every solution[k] s, 1 <= s.xPosition <= i and 
    #1 <= s.yPosition <= i and 1 <= s.value <= i also requires that for any p and q
    #solution[p].yPosition != solution[q].yPosition or solution[p].xPosition != solution[q].xPosition
    #
    #ensures turnSolutionIntoArray = n x n matrix m where for every solution[k] s there exists some m[i][j] where 
    #s.xPosition = i and s.yPosition = j and s.Value = m[i][j] and for every m[i][j] where there does not exist s,
    #m[i][j] = 0
    debug = true
    a = Array.new(i) {Array.new(i) {0}}
    while solution.length > 0
        node = solution.pop()
        x = node.xPosition
        y = node.yPosition
        v = node.value
        a[x-1][y-1] = v
    end
    a
end

def isValidInput(m,a)
    n = m.length
    return false unless a.length == n
    (0...n).each do |i|
        return false unless a[i].length == n
        return false unless m[i].length == n
    end    
end

def getNodes(n)
    #require a non-negative integer n
    #create all possible nodes for n rows, n columns, and n values
    nodes = []
    (1..n).each do |x|
        (1..n).each do |y|
            (1..n).each do |v|                
                node = Node.new(x,y,v)
                nodes.push(node)                
            end
        end
    end
    nodes
end

def backtrack(solution, i, constraints)
    debug = false
    #requires solution where |solution| > i and i is a non-negative integer
    #and for every s in #solution and for every c in s.constraints c is not an element of #constraints and for any
    #p and q in #solution no c in p.constraints is in q.constraints.
    
    #ensures solution = #solution[0..(i-1)] if i >= 1 or empty set if i = 0
    #and for every s in solution, constraints = constraints + s.constraints where for every c in s.constraints 
    #c.nodes intersect solution is the empty set and for every s in #solution [i...#solution.length], for every c in 
    #s.constraints and every n in c.nodes and every c' in n.constraints, n is element of c'.nodes
    print "backtracking to ", i, " from ", solution.length, "\n" if debug
    until solution.length == i
        node = solution.pop()
        fixConstraints(node, constraints)
    end
end

def fixConstraints(node, constraints)
    debug = false
    #requires: node is a Node, constraints is a list of Constraint's and for any
    # c in node.constraints, c is not an element of constraints
    #
    #ensures: for every c in node.constraints, constraints = #constraints + c and for every n in c.nodes
    #and every c' in n.constraints n is an element of c'.nodes 
    #and node = #node
    
    constraintsToPush = Array.new(node.constraints)

    until constraintsToPush.length == 0
        con = constraintsToPush.pop()
        constraints.push(con)
        print "constraint added ",con.description, "\n" if debug
        node.constraints.each do |c|
            uncoverNodesAndConstraints(c)
        end
    end
end

def uncoverNodesAndConstraints(con)
    #requires a Constraint con. This is designed to be used for constraints
    # that have just been fixed with fixConstraint, but it shouldn't make a difference
    #ensures for every n in con.nodes and for every c in n.constraints n is an element of c.nodes 
    con.nodes.each do |node|
        node.constraints.each { |c| c.nodes.push(node) unless c.nodes.include?(node)}
    end

end

def findNextConstraint(constraints)
    #requires a list of constraints where |constraints| > 0
    #returns the constraint with the fewest opportunities to satisfy
    constraint = constraints[0]
    (0...constraints.length).each do |i|
        con = constraints[i]
        constraint = con if con.nodes.length < constraint.nodes.length 
    end
    constraint
end

def printArray(a)
    #requires 2D array of size n x n where n is a positive integer
    #prints it to stdout in nice formatting
    (0...a.length).each do |y|
        a.each do |x|
            print x[y].to_s + ' '
        end
        print "\n"
    end
end

def removeNodesFromConstraint(con)
    # for every node in of con.nodes, 
    # ensure for every c in node.constraints n is not an element of c.nodes unless c = con
    con.nodes.each do |node|
        node.constraints.each { |c| c.nodes.delete(node) unless c == con } 
    end
end

def removeNode(node, constraints)
    #require a node and a list of constraints. For every c in node.constraints, c must be an element of #constraints
    # (This should happen automatically if everything is running as it should)
    #
    #ensures for every c in node.constraints c is not an element of constraints
    #and for every n in #c.nodes n is not an element of any c' in n.constraints unless c = c'
    node.constraints.each do |c|
        unless constraints.include?(c)
            print "Can't delete this constraint ", c.description, " how did you get here???\n"
        end
        constraints.delete(c) if constraints.include?(c)
        removeNodesFromConstraint(c)
    end
end

def findNodes(nodeList, x = 0, y = 0, v = 0)
    #requires a list containing the node that you are searching for
    #x, y, v must be non-negative integers. a 0 would mean ignore that argument
    #returns node you are searching for.
    x = 0 if x == nil
    y = 0 if y == nil
    v = 0 if v == nil
    nodes = nodeList
    nodes = nodes.select { |n| n.xPosition == x } unless x == 0
    nodes = [] unless nodes
    nodes = nodes.select { |n| n.yPosition == y } unless y == 0
    nodes = [] unless nodes
    nodes = nodes.select { |n| n.value == v } unless v == 0
    nodes = [] unless nodes
    nodes
end




def getConstraints(n)
    #requires non-negative integer n
    #returns full set of constraints for an n x n game.
    constraints = []
    
    (1..n).each do |y|
        (1..n).each do |v|
            c = Constraint.new("Row #{y} needs a #{v}")
            c.row = y
            c.value = v
            constraints.push(c)
        end
    end
    
    (1..n).each do |x|
        (1..n).each do |v|
            c = Constraint.new("Column #{x} needs a #{v}")
            c.column = x
            c.value = v
            constraints.push(c)
        end
    end
    
    (1..n).each do |z|
        (1..n).each do |v|
            c = Constraint.new("Group #{z} needs a #{v}")
            c.group = z
            c.value = v
            constraints.push(c)
        end
    end
    
    (1..n).each do |x|
        (1..n).each do |y|
            c = Constraint.new("Box (#{x},#{y}) has a value in it")
            c.filled = true
            c.row = y
            c.column = x
            constraints.push(c)
        end    
    end
    
    constraints
end

def makeGroupList(m)
    #require a n x n matrix m which contains a group map as defined above
    #returns an array of n arrays, each with n elements, each of which is an (x,y) pair that corresponds
    #to the x, y position of that group number in m.
    
    groups = Array.new(m.length) {Array.new(0)}
    
    (0...m.length).each do |x|
        (0...m.length).each do |y|
            groups[m[x][y] - 1].push([x+1,y+1])
        end
    end
    groups
end

def assignNodesToConstraints(nodes, constraints, groupList)
    #require a complete set of nodes for a matrix of size i x i and a complete set of constraints for
    #an n x n game. These are defined above. i must be a positive integer. Also requires a group list
    #return
    #true or false depending on success
    #should modify nodes to have 4 constraints in their list and modify constraints to have i nodes in 
    #their list. Each constraint with a matching attribute to a node should have that node it its list and
    #each node should have a constraint they fulfill in their list.
    
    constraints.each do |c|
        x = 0
        y = 0
        z = 0
        v = 0
        x = c.column if c.column
        y = c.row if c.row
        z = c.group if c.group
        v = c.value
        c.nodes = findNodes(nodes, x, y, v) if z == 0 and not c.filled
        c.nodes = findNodes(nodes, x, y) if c.filled
        unless z == 0
            # Find nodes in group with values v
            valueNodes = findNodes(nodes, 0,0, v)
            groupList[z-1].each do |xy|
                node = findNodes(valueNodes, xy[0], xy[1], v)
                c.nodes.push(node[0])
            end  
        end
        c.nodes.each do |n|
            n.constraints.push(c)
        end        
    end 
end

puts "enter a file name: "
filename = File.join(Dir::pwd,gets[0..-2])
if File.exists?(filename) then
    cells = IO::read(filename).chars.to_a.select! {|c| (1..9).member?(c.to_i) or c == '.'}
    a = Array.new(9) {Array.new(9) {nil}} #2d array represents the puzzle
    n = 0
    for i in 0..8 do
        for j in 0..8 do
            a[i][j] = if cells[n] == '.' then 0 else cells[n].to_i end
            n += 1
        end
    end
    answer = solvePuzzle(a,STD_BOX_MATRIX)
    for i in 0..8 do
        puts "---------------------" if i == 3 or i == 6
        row = ""
        for triple in [0..2,3..5,6..8] do
            for x in answer[i][triple] do
                row << if x == 0 then '.' else x.to_s end + " "
            end
            row << "| " if triple.begin != 6
        end
        puts row
    end
elsif
    puts "file doesn't exist"
end
